//  https://www.lintcode.com/problem/intersection-of-two-linked-lists/description?_from=ladder&&fromId=6

/**
 * Definition of singly-linked-list:
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *        this->val = val;
 *        this->next = NULL;
 *     }
 * }
 */

// https://leetcode-cn.com/problems/intersection-of-two-linked-lists/submissions/

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
//法一：将一个链表连到开头，判断环，返回环入口
    // ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    //     if (!headA || !headB) return NULL;
    //     ListNode *tmp = headA;
    //     while (tmp->next) {
    //         tmp = tmp->next;
    //     }
    //     tmp->next = headA;
    //     ListNode *fast = headB;
    //     ListNode *slow = headB;
    //     while (fast && fast->next) {
    //         fast = fast->next->next;
    //         slow = slow->next;
    //         if (fast == slow) {
    //             fast = headB;
    //             while (fast != slow) {
    //                 fast = fast->next;
    //                 slow = slow->next;
    //             }
    //             tmp->next = NULL;
    //             return fast;
    //         }
    //     }
    //     tmp->next = NULL;
    //     return NULL;
    // }

    // https://leetcode-cn.com/problems/intersection-of-two-linked-lists/solution/tu-jie-xiang-jiao-lian-biao-by-user7208t/
    // 法二：消除两个链表长度差之后，从头一起遍历。第一轮先到结尾的指针，重新指向另一个链表的head，当另一个指针走到结尾时，就消除了长度差。将另一个指针指向另一个链表一起遍历。
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (!headA || !headB) return NULL;
        ListNode *pa = headA;
        ListNode *pb = headB;
        while (pa != pb) {
            pa = pa == NULL? headB: pa->next;
            pb = pb == NULL? headA: pb->next;
        }
        return pa;
    }

    // 法三：哈希表
    // ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    //     unordered_set<ListNode*> s;
    //     ListNode *tmp = headA;
    //     while (tmp) {
    //         s.insert(tmp);
    //         tmp = tmp->next;
    //     }
    //     tmp = headB;
    //     while (tmp) {
    //         if (s.find(tmp) != s.end()) return tmp;
    //         tmp = tmp->next;
    //     }      
    //     return NULL;
    // }
};